import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-08-14
 * Time: 23:24
 */
class Solution7 {
    int[] tmp1;
    int[] tmp2;
    int[] ret;
    int[] index;//标号nums原始下标
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        tmp1 = new int[n];
        tmp2 = new int[n];
        ret = new int[n];
        index = new int[n];

        //初始化
        for(int i = 0; i < n; i++) {
            index[i] = i;
        }

        mergeSort(nums,0,n-1);

        List<Integer> list = new ArrayList<>();

        for(int x : ret) {
            list.add(x);
        }
        return list;
    }

    public void mergeSort(int[] nums,int left,int right) {
        if(left >= right) {
            return;
        }

        int mid = (left+right)/2;

        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);


// 处理一左一右
        int cur1 = left, cur2 = mid+1,i = 0;
        while(cur1 <= mid && cur2 <= right) {  //降序
            if(nums[cur1] <= nums[cur2]) {
                // 值修改
                tmp1[i] = nums[cur2];
                // 下标修改,这样才能对应
                tmp2[i] = index[cur2];
                i++;
                cur2++;
            }else {
                tmp1[i] = nums[cur1];
                tmp2[i] = index[cur1];
                ret[tmp2[i]] += right - cur2 + 1;
                i++;
                cur1++;
            }
        }

        while(cur1 <= mid) {
            tmp1[i] = nums[cur1];
            tmp2[i] = index[cur1];
            i++;
            cur1++;
        }

        while(cur2 <= right) {
            tmp1[i] = nums[cur2];
            tmp2[i] = index[cur2];
            i++;
            cur2++;
        }

        for(int j = left; j <= right; j++) {
            nums[j] = tmp1[j-left];
            index[j] = tmp2[j-left];
        }
    }
}
